Wireless networks have experienced increased development in the past decade. One of the most rapidly developing areas is mobile ad-hoc networks. Physically, a mobile ad-hoc network includes a number of geographically-distributed, potentially mobile nodes sharing a common radio channel. Compared with other types of networks, such as cellular networks or satellite networks, the most distinctive feature of mobile ad-hoc networks is the lack of any fixed infrastructure. The network may be formed of mobile nodes only, and a network is created “on the fly” as the nodes transmit with each other. The network does not depend on a particular node and dynamically adjusts as some nodes join or others leave the network.
Because of these unique characteristics, routing protocols for governing data flow within ad-hoc networks are required which can adapt to frequent topology changes. Two basic categories of ad-hoc routing protocols have emerged in recent years, namely reactive or “on-demand” protocols, and proactive or table-driven protocols. Reactive protocols collect routing information when a particular route is required to a destination in response to a route request. Examples of reactive protocols include ad-hoc on demand distance vector (AODV) routing, dynamic source routing (DSR), and the temporally ordered routing algorithm (TORA).
On the other hand, proactive routing protocols attempt to maintain consistent, up-to-date routing information from each node to every other node in the network. Such protocols typically require each node to maintain one or more tables to store routing information, and they respond to changes in network topology by propagating updates throughout the network to maintain a consistent view of the network. Examples of such proactive routing protocols include destination-sequenced distance-vector (DSDV) routing, which is disclosed in U.S. Pat. No. 5,412,654 to Perkins; the wireless routing protocol (WRP); and cluster head gateway switch routing (CGSR). A hybrid protocol which uses both proactive and reactive approaches is the zone routing protocol (ZRP), which is disclosed in U.S. Pat. No. 6,304,556 to Haas.
One challenge to the advancement of ad-hoc network development is that of extending such networks to encompass large numbers of nodes. One prior art attempt to do so utilizes “spine” routing, such as in the optimal spine routing (OSR) approach disclosed by Das et al. in “Routing in Ad-Hoc Networks using Minimum Connected Dominating Sets,” IEEE Int. Conf. On Commun. (ICC '97), 1997. In this approach, a spine or “virtual backbone” is defined such that each network node is no more than one hop from a spine node. Global topology (link state) is maintained at each spine node, and a link-state routing algorithm is run at each spine node to produce current routes to every destination.
Another related approach is clustered spine routing (CSR), which is disclosed by Das et al. in “Routing in Ad-Hoc Networks using a Spine,” IEEE Int. Conf. On Computer Commun. and Networks (IC3N '97), 1997 this approach is intended to extend the applicability of spine routing to larger network sizes by grouping the nodes in clusters and adding a second hierarchical level to the OSR approach. Yet another approach is known as partial knowledge spine routing (PSR) which is disclosed by Sivakumar et al. in “The Clade Vertebrata: Spines and Routing in Ad-Hoc Networks,” IEEE Symposium On Computer and Commun., 1998.
In an ad hoc network, a cluster is a group of nodes that are topologically connected and share a membership in the group. The cluster could span 1-hop or multiple hops. The header node of the cluster has certain specific functions that benefit the cluster and may be referred to as the cluster head or Group Server Node (GSN). Any node may become the GSN and the GSN's node ID may be used for the group ID. There should be only one GSN in the group and a new GSN should be elected if the current GSN is powered down or leaves the network or group.
The approach used to elect a GSN should be a distributed method since nodes in the network only have local knowledge. No single node should be manually pre-selected to arbitrate which node should be the next GSN. The approach should also be robust since, in an ad-hoc network with nodes coming and leaving, powering down and disappearing, the topology is changing. The GSN may be re-elected. Problems include that the election method may result in electing more than one GSN, or electing no GSN. The elected GSN may become inaccessible, due to the asymmetrical links, unstable links, breaking of communication handshaking. If more than one GSN is elected, some of them have to give up the status. Also, the election process may require the nodes to consume a lot of bandwidth, as system overhead.
GSN election, group merging and timing may not be supported. The GSN is the timing reference node. During group merging, part of the nodes in one group are switching to a new group, and a simultaneous change in the network timing may also be happening. If a GSN election is also in progress, the nodes become confused as to which node holds the right timing and how many GSNs may be coexisting in this mixed state.
Also, during the GSN election, part of the network may be separated out into more than one sub-group and an elected GSN may be not reachable in some separated sub-groups. Furthermore, a GSN may be partially departed from the network, leaving an asymmetrical link connected to the cluster. The cluster nodes can all hear the GSN but cannot send to the GSN. The new GSN election must be able to proceed under the asymmetrical link influence of the previous GSN. The member nodes should not forever exclude the previous GSN into the group as the previous GSN should be allowed to come back as a regular member node.
One approach that addresses some of these problems is the Low-energy localized clustering (LLC) algorithm. Any node that does not see another node declared as cluster head in the local neighborhood for a certain time will just declare itself as a cluster head. Multiple cluster heads could be elected in a multi-hopped network. In the process, each node sends an advertisement message to declare its membership so the approach is not bandwidth efficient. If acknowledgments are included in the approach, more bandwidth is consumed. Some messages could be dropped due to unstable links, and an asymmetrical link could result in an unreachable cluster head. Moreover, in this LLC approach, the cluster is confirmed to a 2-hop neighbor type only, and many clustering approaches may span more than 2-hops.
Another approach is the Low Energy Adaptive Clustering Hierarchy (LEACH) Algorithm which is a more bandwidth efficient method. Periodically a node abandons the existing cluster head and declares itself as a cluster head with a probability. This method does not require a lot of message exchange but could result in multiple cluster heads, or no cluster head. So, this approach may not be suitable for many applications.